/*
 * @Description  : 
 * @Autor        : yanwang
 * @CreateDate   : 2021-11-11 09:37:55
 * @LastEditors  : yanwang
 * @LastEditTime : 2021-11-11 18:04:56
 */

/**
 * @param {number[]} nums
 * @return {number}
 */

class TrieNode {
  next = [null, null];
}
class Trie {
  root = new TrieNode();

  insert(x) {
    let p = this.root;
    for (let i = 30; i >= 0; i--) { // JS是31位数，所以右移30位
      let ind = !!(x & (1 << i)); // 对 x 的 i 位异或
      if(p.next[ind] === null) p.next[ind] = new TrieNode();
      p = p.next[ind];
    }
  }

  search(x) {
    let p = this.root;
    let ans = 0;
    for (let i = 30; i >= 0; i--) {
      let ind = !!(x & (1 << i)); // 将 x 的 i 位异或，然后去字典树中查询
      if(p.next[!ind]) {
        ans |= (1 << i); // 将ans第i为置为 1;
        p = p.next[!ind];
      } else {
        p = p.next[ind];
      }
    }
    
    return ans;
  }

}

// 将 num 的各位的 异或结果 插入字典树中
var findMaximumXOR = function(nums) {
  let trie = new Trie();
  for(let num of nums) {
    trie.insert(num);
  }

  let ans = 0;
  for(let num of nums) {
    ans = Math.max(ans, trie.search(num));
  }
  return ans;
};



var findMaximumXOR = function(nums) {
  let root = {
    0: undefined,
    1: undefined,
  }; // 树根，用对象的嵌套实现树
  
  for(let num of nums) {
    let cur = root;
    let bit = 0;
    // 从高到低，按位插入树中。
    for (let i = 30; i >= 0; i--) {
      bit = (num >> i) & 1; // 取高位 数字
      if(cur[bit] === undefined) cur[bit] = {};
      cur = cur[bit];
    }
  }

  let ans = 0;
  for(let num of nums) {
    let cur = root;
    let res = 0;

    for (let i = 30; i >= 0; i--) {
      let bit = (num >> i) & 1; // 取高位 数字
      if(cur[1] && (1 ^ bit === 1)) { // 树中存在为 1 的此高位， 且与num此位异或可以得到1
        res = (res << 1) + 1;
        cur = cur[1];
      } else if(cur[0] && (0 ^ bit === 1)) { // 树中存在为 0 的此高位， 且与num此位异或可以得到1
        res = (res << 1) + 1;
        cur = cur[0];
      } else { // 次高位异或无法得到 1 
        res = res << 1;
        cur = cur[bit];
      }
    }
    if(res > ans) ans = res;
  }
  return ans;
}
